/*************************************************************************
 * File Name:    Spiral_Matrix.cc
 * Author:       zero91
 * Mail:         jianzhang9102@gmail.com
 * Created Time: 2013/11/17 23:03:26
 * 
 * Description:  
 |------------------------------------------------------------------------
 | Problem: Spiral Matrix
 |
 | Given a matrix of m x n elements (m rows, n columns),
 | return all elements of the matrix in spiral order.
 |
 | For example,
 | Given the following matrix:
 |
 | [
 |   [ 1, 2, 3 ],
 |   [ 4, 5, 6 ],
 |   [ 7, 8, 9 ]
 | ]
 | You should return [1,2,3,6,9,8,7,4,5].
 |------------------------------------------------------------------------
 ************************************************************************/

#include <iostream>
#include <fstream>
#include <sstream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <deque>
#include <map>
#include <set>
#include <functional>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>

using namespace std;

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int> > &matrix)
    {
        if (matrix.size() == 0) return vector<int>();
        
        int m = matrix.size();
        int n = matrix[0].size();
        
        vector<int> ans;
        int lim = min(m / 2, n / 2);
        
        for (int i = 0; i < lim; ++i) {
            for (int j = i; j < n - i; ++j) ans.push_back(matrix[i][j]);
            
            for (int j = i + 1; j < m - i - 1; ++j) ans.push_back(matrix[j][n - i - 1]);
            
            for (int j = n - i - 1; j >= i; --j) ans.push_back(matrix[m - i - 1][j]);
        
            for (int j = m - i - 2; j >= i + 1; --j) ans.push_back(matrix[j][i]);
        }
        if (m >= n && (n & 1)) {
            for (int i = lim; i < m - lim; ++i) {
                ans.push_back(matrix[i][lim]);
            }
        } else if (n > m && (m & 1)) {
            for (int i = lim; i < n - lim; ++i) {
                ans.push_back(matrix[lim][i]);
            }
        }
        return ans;
    }
};

